题解 洛谷 P2376 [USACO09OCT] Allowance G

P2376 [USACO09OCT] Allowance G

简要题意

给你 $n$ 种面值的货币，其中货币中面值小的货币的面值可以整除面值大的货币的面值，给你每种面值货币的数量。每周都要给贝茜发至少 $c$ 元的工资，问最多能发多少周。

策略分析

首先对于面值大于 $c$ 的货币，显然我们每周给出一张就行了，没有其它办法，所以可以直接把它们的数量加在答案中。接下来是对于面值小于 $c$ 的货币，我们先对所有货币按照面值降序排序，每次选取能够选的最大的，然后再用最小的去填补剩下的那一点点价格缝隙，因为我们有小面值货币面值是大面值货币面值因数这个条件，所以最大配最小这种做法一定会产生最小的浪费，从而得到最优解。如果这一次凑不出来了，那显然是钱不够了，那么所有情况就统计完毕，输出答案即可。

参考代码

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#define PII pair<int, int>
using namespace std;

namespace SHAWN {
    vector<PII> v;
    //v.first 代表面值，v.second 代表货币数量
    int n, c, ans; 
    bool cmp(PII x, PII y) { return x.first > y.first; }
    int work()
    {
        cin >> n >> c;
        for (int i = 1, val, b; i <= n; ++i) {
            cin >> val >> b;
            if (val >= c) { ans += b; }
            else { v.push_back({val, b}); }
        }
        sort(v.begin(), v.end(), cmp);
        while (true) {
            int tmp = c;
            for (int i = 0; i < v.size(); ++i) {
                while (tmp && v[i].second && tmp >= v[i].first) {
                    tmp -= v[i].first; 
                    --v[i].second;
                }
            }
            if (tmp > 0) {
                for (int i = v.size() - 1; i >= 0; --i) {
                    if (v[i].second && v[i].first >= tmp) {
                        tmp -= v[i].first;
                        --v[i].second;
                        break;
                    }
                }
            }
            if (tmp > 0) { break; }
            ++ans;
        }
        cout << ans << '\n';
        return 0;
    }
}

signed int main() {
    ios :: sync_with_stdio(false);
    cin.tie(nullptr);
    return SHAWN :: work();
}